package com.mystudy.leetcode.problem.sort.p_147;

/**
 * @program: infoalgorithm
 * @description: 对链表进行插入排序
 * @author: zhouzhilong
 * @create: 2019-08-02 14:44
 **/

import com.mystudy.leetcode.base.ListNode;
import com.mystudy.leetcode.base.ListNodeUtils;
import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.concurrent.TimeUnit;

/**
 * 插入排序算法：
 * <p>
 * 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
 * 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
 * 重复直到所有输入数据插入完为止。
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入: 4->2->1->3
 * 输出: 1->2->3->4
 * 示例 2：
 * <p>
 * 输入: -1->5->3->4->0
 * 输出: -1->0->3->4->5
 */

public class Solution {
    private static final Logger LOGGER = LoggerFactory.getLogger(Solution.class);

    @Warmup(iterations = 3, time = 1)
    @Measurement(iterations = 3, time = 1)
    @Benchmark
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.MICROSECONDS)
    public void test() {
        ListNode listNode = ListNodeUtils.generateLinkList(new int[]{-1, 5, 3, 4, 0,5,2, 5,9,0,5,1,4,2,61,23,61,22,});
        ListNode result = insertionSortList(listNode);
//        ListNodeUtils.show(result);
    }


    public ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode prev = dummyHead;
        ListNode cur = head;
        while (cur.next != null) {
            if (prev.next.val > cur.next.val) {
                ListNode temp = cur.next;
                cur.next = temp.next;
                temp.next = prev.next;
                prev.next = temp;
                prev = dummyHead;
            } else {
                prev = prev.next;
                if (prev == cur) {
                    cur = cur.next;
                    prev = dummyHead;
                }
            }
        }
        return dummyHead.next;
    }


    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
                .include(Solution.class.getSimpleName())
                .forks(1)
                .build();

        new Runner(opt).run();
    }
}
